Hash tables are data structures used in many high performance systems. Such systems may be highly concurrent and may run on multi-core central processing units (CPUs). Examples of such systems include web servers, database servers, and directory servers. For example, a hash table may be used for fast lookup in a (software) cache that includes frequently used items. The number of items in a cache may vary greatly, both over time and among installations.
Linear hashing is a technique for gradually increasing or decreasing the size of a hash table as the number of items changes so that the expected cost of operations (e.g., insert, lookup, delete) is O(1). Linear hashing may gradually expand a hash table by splitting buckets and may contract the table by merging buckets. The items included in a bucket may be stored on a single linked list. Buckets may be split (and merged) in a fixed order. During a split, approximately half of the items in the bucket may be relocated to a new bucket at the end of the hash table. For example, a bucket split may involve scanning the items in the bucket and re-computing their hash addresses to determine which items stay in the current bucket and which items will be relocated to the new bucket.